package ua.yandex.collections;

import java.util.Arrays;
import java.util.Comparator;

public class MyCollections {

    // Reverses the order of the elements in the specified list
    public static void reverse(MyList list) {
        Object[] array = list.toArray();
        Object[] newArray = new Object[array.length];
        for (int i = 0; i < array.length; i++) {
            newArray[i] = array[array.length - i - 1];
        }
        list.clear();
        list.addAll(newArray);
    }

    private static int binarySearch(Comparable[] array, Object key) {
        if (array.length == 0) {
            return -1;
        }
        int i = (array.length - 1) / 2;
        if (array[i].compareTo(key) == 0) {
            while (i >= 0 && array[i].compareTo(key) == 0) {
                i--;
            }
            return i + 1;
        } else {
            if (array[i].compareTo(key) < 0) {
                int result = binarySearch(Arrays.copyOfRange(array, i + 1, array.length), key);
                if (result >= 0) {
                    return i + 1 + result;
                } else {
                    return result - i - 1;
                }
            } else { //if (copyArray[i].compareTo(key) > 0) 
                return binarySearch(Arrays.copyOfRange(array, 0, i), key);
            }
        }
    }

    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key) {
        Object[] array = list.toArray();
        Comparable[] copyArray = new Comparable[array.length];
        for (int i = 0; i < array.length; i++) {
            copyArray[i] = (Comparable) array[i];
        }
        return binarySearch(copyArray, key);
        //Если элемент найден, то возвращается его индекс. 
        //Если не найдет, то возвращается отрицательное значение, вычисляемое по следующей формуле: 
        //(-(insertion point) - 1), где insertion point - индекс того места в массиве, где должен был бы быть указанный элемент.
    }

    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    private static int binarySearch(Object[] array, Object key, Comparator cp) {
        if (array.length == 0) {
            return -1;
        }
        int i = (array.length - 1) / 2;
        if (cp.compare(array[i], key) == 0) {
            while (i >= 0 && cp.compare(array[i], key) == 0) {
                i--;
            }
            return i + 1;
        } else {
            if (cp.compare(array[i], key) < 0) {
                int result = binarySearch(Arrays.copyOfRange(array, i + 1, array.length), key, cp);
                if (result >= 0) {
                    return i + 1 + result;
                } else {
                    return result - i - 1;
                }
            } else { //if (copyArray[i].compareTo(key) > 0) 
                return binarySearch(Arrays.copyOfRange(array, 0, i), key, cp);
            }
        }
    }

    public static int binarySearch(MyList list, Object key, Comparator cp) {
        Object[] array = list.toArray();
        return binarySearch(array, key, cp);
    }
}
